package leetcode.weekly.week324;

import java.util.ArrayList;
import java.util.List;

//Solution4Test
public class Solution4 {

	public int[] cycleLengthQueries(int n, int[][] queries) {
		int[] ans = new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			int[] q = queries[i];
			int a = q[0], b = q[1];
			if (a == b) {
				ans[i] = 1;
			} else if (a / 2 == b / 2) {
				ans[i] = 3;
			} else if (same(a, b)) {
				ans[i] = samepath(a, b);
			} else {
				int root = root(a, b);
				ans[i] = log2(a) + log2(b) + 1 - log2(root) * 2;
			}
		}
		return ans;
	}

	private int samepath(int a, int b) {
		int min = Math.min(a, b);
		int max = Math.max(a, b);
		return log2(max) - log2(min) + 1;
	}

	private boolean same(int a, int b) {
		int min = Math.min(a, b);
		int max = Math.max(a, b);
		while (max > min) {
			max /= 2;
		}
		return max == min;
	}

	private int root(int a, int b) {
		List<Integer> list = new ArrayList<>();
		while (a > 0) {
			list.add(a);
			a /= 2;
		}
		while (b > 0) {
			if (list.contains(b)) {
				return b;
			}
			b /= 2;
		}
		return 1;
	}

	public int log2(int q) {
		return (int) (Math.log(q) / Math.log(2));
	}
}
